//给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 
//
//
// 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。 
//
//
// 
// 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。 
// 
//
// 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。 
//
// 
//
// 示例 1： 
//
// 
//输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
//输出：["JFK","MUC","LHR","SFO","SJC"]
// 
//
// 示例 2： 
//
// 
//输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL",
//"SFO"]]
//输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
//解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= tickets.length <= 300 
// tickets[i].length == 2 
// fromi.length == 3 
// toi.length == 3 
// fromi 和 toi 由大写英文字母组成 
// fromi != toi 
// 
// Related Topics 深度优先搜索 图 欧拉回路 👍 550 👎 0

package leetcode.editor.cn;

import java.util.*;

class ReconstructItinerary {
    public static void main(String[] args) {
        Solution solution = new ReconstructItinerary().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public List<String> findItinerary(List<List<String>> tickets) {
        // 封装数据为 Map<出发机场, map<到达机场, 航班次数>>
        for (List<String> ticket : tickets) {   // 防止出现null
            Map<String, Integer> tempMap;
            if (map.containsKey(ticket.get(0))) {
                tempMap = map.get(ticket.get(0));
                tempMap.put(ticket.get(1), tempMap.getOrDefault(ticket.get(1), 0) + 1);
            } else {
                tempMap = new TreeMap<>();  // 升序Map
                tempMap.put(ticket.get(1), 1);
            }
            map.put(ticket.get(0), tempMap);
        }
        path.add("JFK");    // 开始地方
        backtracking(tickets.size());
        return new ArrayList<>(path);
    }

    Map<String, Map<String, Integer>> map = new HashMap<>();
    LinkedList<String> path = new LinkedList<>();

    */
        /**
         * 回溯求线路
         *
         * @param ticketNum 表示有多少个航班
         * @return 此时只需要一条线路，返回值为Boolean即可
         */
    /*public boolean backtracking(int ticketNum) {
        if (path.size() == ticketNum + 1) {
            return true;    // 线路等于航班加一时满足一圈航程
        }

        String last = path.get(path.size() - 1);  // 获取上一个站台，来进行下一次的选择
        if (map.containsKey(last)) {
            for (Map.Entry<String, Integer> entry : map.get(last).entrySet()) { // 这个站台的航班
                Integer count = entry.getValue(); // 表示航班数量
                if (count > 0) {    // 此时可以飞到此站
                    path.add(entry.getKey());
                    entry.setValue(count - 1);// 此路程的票数减一
                    if (backtracking(ticketNum)) return true;   // 如果此时搜索到一条线路则停止搜索
                    path.removeLast();  // 回溯
                    entry.setValue(count);// 恢复路程的票数
                }
            }
        }
        return false;
    }*/

        Map<String, Map<String, Integer>> map = new HashMap<>();
        LinkedList<String> res = new LinkedList<>();

        public List<String> findItinerary(List<List<String>> tickets) {
            Map<String, Map<String, Integer>> map = new HashMap<>();
            for (List<String> ticket : tickets) {
                String from = ticket.get(0);
                map.putIfAbsent(from, new TreeMap<>());
                String to = ticket.get(1);
                map.get(from).put(to, map.get(from).getOrDefault(to, 0) + 1);
            }
            res.add("JFK");
            backtracking(map, tickets.size());
            return res;
        }

        private boolean backtracking(Map<String, Map<String, Integer>> map, int ticketNum) {
            if (res.size() == ticketNum + 1) {
                return true;
            }

            String last = res.getLast();
            if (map.containsKey(last)) {
                for (Map.Entry<String, Integer> entry : map.get(last).entrySet()) {
                    Integer count = entry.getValue();
                    if (count > 0) {
                        res.add(entry.getKey());
                        entry.setValue(count - 1);
                        if (backtracking(map, ticketNum)) return true;
                        entry.setValue(count);
                        res.removeLast();
                    }
                }
            }
            return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
